/*
 * @(#)DefaultSolver.java
 */
package jp.ac.kobe_u.cs.cream;

import jp.ac.kobe_u.cs.cream.*;
import java.util.*;

/**
 * A branch-and-bound solver.
 * @see	Solver
 * @since 1.0
 * @version 1.0, 01/31/03
 * @author Naoyuki Tamura (tamura@kobe-u.ac.jp)
 */
public class DefaultSolver extends Solver {
    protected Trail trail = new Trail();

    private static final int STEP = 0;
    private static final int ENUM = 1;
    private static final int BISECT = 2;
    private int choice = STEP;

    /**
     * Constructs a branch-and-bound solver for the given network.
     * This constructor is equivalent to <tt>DefaultSolver(network, DEFAULT, null)</tt>.
     * @param network the constraint network
     */
    public DefaultSolver(Network network) {
	this(network, DEFAULT, null);
    }

    /**
     * Constructs a branch-and-bound solver for the given network and options.
     * This constructor is equivalent to <tt>DefaultSolver(network, options, null)</tt>.
     * @param network the constraint network
     * @param options the options for search strategy
     */
    public DefaultSolver(Network network, int options) {
	this(network, options, null);
    }

    /**
     * Constructs a branch-and-bound solver for the given network and name.
     * This constructor is equivalent to <tt>DefaultSolver(network, DEFAULT, name)</tt>.
     * @param network the constraint network
     * @param name the name of the solver
     */
    public DefaultSolver(Network network, String name) {
	this(network, DEFAULT, name);
    }

    /**
     * Constructs a branch-and-bound solver for the given network, options, and name.
     * @param network the constraint network
     * @param options the options for search strategy, or DEFAULT for default search strategy
     * @param name the name of the solver, or <tt>null</tt> for a default name
     */
    public DefaultSolver(Network network, int options, String name) {
	super(network, options, name);
    }

    private List modifiedConstraints() {
	List list = new LinkedList();
	Iterator cs = network.getConstraints().iterator();
	while (cs.hasNext()) {
	    Constraint c = (Constraint)cs.next();
	    if (c.isModified()) {
		list.add(c);
	    }
	}
	Iterator vs = network.getVariables().iterator();
	while (vs.hasNext()) {
	    Variable v = (Variable)vs.next();
	    v.clearModified();
	}
	return list;
    }

    protected boolean satisfy() {
	boolean changed = true;
	while (! isAborted() && changed) {
	    Iterator cs = modifiedConstraints().iterator();
	    while (cs.hasNext()) {
		Constraint c = (Constraint)cs.next();
		if(! c.satisfy(trail)) {
		    return false;
		}
	    }
	    changed = false;
	    Iterator vs = network.getVariables().iterator();
	    while (! changed && vs.hasNext()) {
		changed |= ((Variable)vs.next()).isModified();
	    }
	}
	return true;
    }

    protected Variable infVariable() {
	Variable v_min = null;
	int inf_min = Integer.MAX_VALUE;
	int inf;
	Iterator vs = network.getVariables().iterator();
	while (vs.hasNext()) {
	    Variable v = (Variable)vs.next();
	    Domain d = v.getDomain();
	    if (! (d instanceof IntDomain))
		continue;
	    if (d.size() <= 1)
		continue;
	    inf = ((IntDomain)d).min();
	    if (inf < inf_min) {
		v_min = v;
		inf_min = inf;
	    }
	}
	return v_min;
    }

    protected Variable minimumSizeVariable() {
	Variable v_min = null;
	int min_size = Integer.MAX_VALUE;
	Iterator vs = network.getVariables().iterator();
	while (vs.hasNext()) {
	    Variable v = (Variable)vs.next();
	    int size = v.getDomain().size();
	    if (1 < size && size <= min_size) {
		v_min = v;
		min_size = size;
	    }
	}
	return v_min;
    }

    protected Variable selectVariable() {
	Variable v = null;
	if (isOption(MINIMIZE) || isOption(MAXIMIZE)) {
	    v = infVariable();
	    // v = minimumSizeVariable();
	}
	if (v == null) {
	    v = minimumSizeVariable();
	}
	return v;
    }

    protected void solve(int level) {
	Variable objective = network.getObjective();
	while (! isAborted()) {
	    if (isOption(MINIMIZE)) {
		if (bestValue < IntDomain.MAX_VALUE) {
		    IntDomain d = (IntDomain)objective.getDomain();
		    d = (IntDomain)d.delete(bestValue, IntDomain.MAX_VALUE);
		    if (d.isEmpty())
			break;
		    objective.updateDomain(d, trail);
		}
	    } else if (isOption(MAXIMIZE)) {
		if (bestValue > IntDomain.MIN_VALUE) {
		    IntDomain d = (IntDomain)objective.getDomain();
		    d = (IntDomain)d.delete(IntDomain.MIN_VALUE, bestValue);
		    if (d.isEmpty())
			break;
		    objective.updateDomain(d, trail);
		}
	    }
	    boolean sat = satisfy();
	    if (isAborted() || ! sat)
		break;
	    Variable v0 = selectVariable();
	    if (v0 == null) {
		solution = new Solution(network);
		success();
		break;
	    }
	    if (v0.getDomain() instanceof IntDomain) {
		IntDomain d = (IntDomain)v0.getDomain();
		switch (choice) {
		case STEP:
		    int value = d.min();
		    if (! isAborted()) {
			int t0 = trail.size();
			v0.updateDomain(new IntDomain(value), trail);
			solve(level + 1);
			trail.undo(t0);
		    }
		    if (! isAborted()) {
			v0.updateDomain(d.delete(value), trail);
			continue;
		    }
		    break;
		case ENUM:
		    Iterator iter = v0.getDomain().elements();
		    while (! isAborted() && iter.hasNext()) {
			int t0 = trail.size();
			v0.updateDomain((Domain)iter.next(), trail);
			solve(level + 1);
			trail.undo(t0);
		    }
		    break;
		case BISECT:
		    int mid;
		    if (d.min() + 1 == d.max())
			mid = d.min();
		    else
			mid = (d.min() + d.max()) / 2;
		    if (! isAborted()) {
			int t0 = trail.size();
			v0.updateDomain(d.capInterval(d.min(), mid), trail);
			solve(level + 1);
			trail.undo(t0);
		    }
		    if (! isAborted()) {
			int t0 = trail.size();
			v0.updateDomain(d.capInterval(mid + 1, d.max()), trail);
			solve(level + 1);
			trail.undo(t0);
		    }
		    break;
		}
	    } else {
		Iterator iter = v0.getDomain().elements();
		while (! isAborted() && iter.hasNext()) {
		    int t0 = trail.size();
		    v0.updateDomain((Domain)iter.next(), trail);
		    solve(level + 1);
		    trail.undo(t0);
		}
	    }
	    break;
	}
    }

//      protected void solve(int level) {
//  	if (isAborted())
//  	    return;
//  	Variable objective = network.getObjective();
//  	if (isOption(MINIMIZE)) {
//  	    if (bestValue < IntDomain.MAX_VALUE) {
//  		IntDomain d = (IntDomain)objective.getDomain();
//  		d = (IntDomain)d.delete(bestValue, IntDomain.MAX_VALUE);
//  		if (d.isEmpty())
//  		    return;
//  		objective.updateDomain(d, trail);
//  	    }
//  	} else if (isOption(MAXIMIZE)) {
//  	    if (bestValue > IntDomain.MIN_VALUE) {
//  		IntDomain d = (IntDomain)objective.getDomain();
//  		d = (IntDomain)d.delete(IntDomain.MIN_VALUE, bestValue);
//  		if (d.isEmpty())
//  		    return;
//  		objective.updateDomain(d, trail);
//  	    }
//  	}
//  	boolean sat = satisfy();
//  	if (isAborted() || ! sat)
//  	    return;
//  	Variable v0 = selectVariable();
//  	if (v0 == null) {
//  	    solution = new Solution(network);
//  	    success();
//  	} else if (v0.getDomain() instanceof IntDomain) {
//  	    IntDomain d = (IntDomain)v0.getDomain();
//  	    int t0 = trail.size();
//  	    int choice = d.min();
//  	    if (! isAborted()) {
//  		v0.updateDomain(new IntDomain(choice), trail);
//  		solve(level + 1);
//  		trail.undo(t0);
//  	    }
//  	    if (! isAborted()) {
//  		v0.updateDomain(d.delete(choice), trail);
//  		solve(level + 1);
//  		trail.undo(t0);
//  	    }
//  	} else {
//  	    Iterator iter = v0.getDomain().elements();
//  	    while (! isAborted() && iter.hasNext()) {
//  		int t0 = trail.size();
//  		v0.updateDomain((Domain)iter.next(), trail);
//  		solve(level + 1);
//  		trail.undo(t0);
//  	    }
//  	}
//      }

    public void run() {
	clearBest();
	trail = new Trail();
	solve(0);
	trail.undo(0);
	fail();
    }

}
